#include<iostream>
#include<vector>
#include <queue>

using namespace std;

class Solution {
public:
    int countPath(vector<vector<int> >& CityMap, int n, int m) {
        int dx[4] = { 0,0,1,-1 };
        int dy[4] = { 1,-1,0,0 };
        queue<pair<int, int>> q;
        vector<vector<int>> path(n, vector<int>(m));
        vector<vector<int>> dist(n, vector<int>(m, -1));
        int x, y, edx, edy;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (CityMap[i][j] == 1)
                {
                    dist[i][j] = 0;
                    path[i][j] = 1;
                    q.push({ i,j });
                }
                else if (CityMap[i][j] == 2)
                    x = i, y = j;

        while (q.size())
        {
            auto t = q.front();
            q.pop();

            for (int j = 0; j < 4; j++)
            {
                int a = t.first + dx[j];
                int b = t.second + dy[j];
                if (a < 0 || b < 0 || a >= n || b >= m)  continue;
                if (CityMap[a][b] == -1) continue;

                if (dist[a][b] == -1)
                {
                    dist[a][b] = dist[t.first][t.second] + 1;
                    path[a][b] = path[t.first][t.second];
                    q.push({ a,b });
                }
                else if (dist[a][b] == dist[t.first][t.second] + 1)
                {
                    path[a][b] += path[t.first][t.second];
                }
            }
        }
        return path[x][y];
    }
};